package linkedlist;

import datastructure.ListNode;
/**
 * https://leetcode-cn.com/problems/reverse-linked-list/
 */
public class E206_ReverseLinkedList {
    // 时间复杂度 O(n) 空间复杂度 O(1)
    public ListNode reverseList(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        // 头节点为空 or 只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        /**
         * [dummyHead]-->[head]-->[1]-->[2]-->[3]-->...-->[x]-->null
         * 
         * prevNode - 反转的头节点
         * curNode - 待排序的节点
         * nextNode - 反转头节点的下一个节点
         * 在prevNode ~ nextNode之间插入 
         * 
         * [prevNode(dummyHead)]-->[nextNode(head)]-->null 
         * [currNode(1)]-->[2]-->[3]-->...-->[x]-->null
         */
        ListNode prevNode = dummyHead, nextNode = head, currNode = head.next;
        nextNode.next = null;
        while (currNode != null) {
            prevNode.next = currNode;
            currNode = currNode.next;
            prevNode.next.next = nextNode;

            nextNode = prevNode.next;
        }
        return dummyHead.next;
    }
}
